// 筛法求莫比乌斯函数
// 相关帖子 ：https://www.cnblogs.com/dx123/p/16717267.html
// 相关帖子 ：https://oi-wiki.org/math/number-theory/sieve/

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000001;
int cnt;
int prime[MAXN];
bool visited[MAXN];
int mu[MAXN];

// 试除法求莫比乌斯函数
int mu1(int n)
{
    if(n <= 1) return n;
    int ans = 0; // ans 为 n 的不同质因子的个数
    for(int i = 2; i <= n / i; ++i)
    {
        if(n % i == 0)
        {
            int count = 0; // 记录 i 这个质因子有多少个
            while(n % i == 0)
            {
                ++count;
                n /= i;
            }
            if(count >= 2) return 0;
            else ++ans;
        }
    }
    if(n > 1) ++ans;

    if(ans % 2 == 0) return 1;
    else return -1;
}

// 筛法求莫比乌斯函数
void mu2(int n)
{
    mu[1] = 1;
    for(int i = 2; i <= n; ++i)
    {
        if(!visited[i])
        {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1; 1LL * i * prime[j] <= n; ++j)
        {
            int m = i * prime[j];
            visited[m] = true;
            if(i % prime[j] == 0)
            {
                mu[m] = 0;
                break;
            }
            else
            {
                mu[m] = -mu[i];
            }
        }
    }
}

int main()
{
    srand(time(nullptr));
    int testTime = 100000;
    mu2(MAXN - 1);
    for(int i = 0; i < testTime; ++i)
    {
        // 生成随机数据进行验证
        int n = rand() % MAXN;
        if(mu1(n) != mu[n]) cout << "出错了！" << endl;
    }

    return 0;
}